home *** CD-ROM | disk | FTP | other *** search
/ 3D GFX / 3D GFX.iso / amiutils / i_l / irit5 / cagd_lib / bsp_knot.c < prev    next >
Encoding:
C/C++ Source or Header  |  1995-12-31  |  67.2 KB  |  1,407 lines
  1. /******************************************************************************
  2. * Bsp_knot.c - Various bspline routines to handle knot vectors.              *
  3. *******************************************************************************
  4. * Written by Gershon Elber, Aug. 90.                          *
  5. ******************************************************************************/
  6.  
  7. #include <ctype.h>
  8. #include <stdio.h>
  9. #include <string.h>
  10. #include "cagd_loc.h"
  11.  
  12. #define KNOT_IS_THE_SAME 1e-10
  13.  
  14. /*****************************************************************************
  15. * DESCRIPTION:                                                               M
  16. * Returns TRUE iff the given curve has no interior knot open end KV.         M
  17. *                                                                            *
  18. * PARAMETERS:                                                                M
  19. *   Crv:        To check for KV that mimics Bezier polynomial curve.         M
  20. *                                                                            *
  21. * RETURN VALUE:                                                              M
  22. *   CagdBType:  TRUE if same as Bezier curve, FALSE otherwise.               M
  23. *                                                                            *
  24. * KEYWORDS:                                                                  M
  25. *   BspCrvHasBezierKV, conversion                                            M
  26. *****************************************************************************/
  27. CagdBType BspCrvHasBezierKV(CagdCrvStruct *Crv)
  28. {
  29.     return BspKnotHasBezierKV(Crv -> KnotVector, Crv-> Length, Crv -> Order);
  30. }
  31.  
  32. /*****************************************************************************
  33. * DESCRIPTION:                                                               M
  34. * Returns TRUE iff the given surface has no interior knot open end KVs.         M
  35. *                                                                            *
  36. * PARAMETERS:                                                                M
  37. *   Srf:       To check for KVs that mimics Bezier polynomial surface.       M
  38. *                                                                            *
  39. * RETURN VALUE:                                                              M
  40. *   CagdBType:  TRUE if same as Bezier curve, FALSE otherwise.               M
  41. *                                                                            *
  42. * KEYWORDS:                                                                  M
  43. *   BspSrfHasBezierKVs, conversion                                           M
  44. *****************************************************************************/
  45. CagdBType BspSrfHasBezierKVs(CagdSrfStruct *Srf)
  46. {
  47.     return
  48.     BspKnotHasBezierKV(Srf -> UKnotVector, Srf-> ULength, Srf -> UOrder) &&
  49.     BspKnotHasBezierKV(Srf -> VKnotVector, Srf-> VLength, Srf -> VOrder);
  50. }
  51.  
  52. /*****************************************************************************
  53. * DESCRIPTION:                                                               M
  54. * Returns TRUE iff the given knot vector has no interior knots and it has    M
  55. * an open end cond.                                                          M
  56. *                                                                            *
  57. * PARAMETERS:                                                                M
  58. *   KnotVector:   To check for open end and no interior knots conditions.    M
  59. *   Len:          Of knot vector.                                            M
  60. *   Order:        Of curve/surface the exploits this knot vector.            M
  61. *                                                                            *
  62. * RETURN VALUE:                                                              M
  63. *   CagdBType:    TRUE if has open end conditions and no interior knots,     M
  64. *                 FALSE otherwise.                                           M
  65. *                                                                            *
  66. * KEYWORDS:                                                                  M
  67. *   BspKnotHasBezierKV, knot vectors, conversion                             M
  68. *****************************************************************************/
  69. CagdBType BspKnotHasBezierKV(CagdRType *KnotVector, int Len, int Order)
  70. {
  71.     return Len == Order * 2 && BspKnotHasOpenEC(KnotVector, Len, Order);
  72. }
  73.  
  74. /*****************************************************************************
  75. * DESCRIPTION:                                                               M
  76. * Returns TRUE iff the given Bspline curve has open end coditions.         M
  77. *                                                                            *
  78. * PARAMETERS:                                                                M
  79. *   Crv:      To check for open end conditions.                              M
  80. *                                                                            *
  81. * RETURN VALUE:                                                              M
  82. *   CagdBType:  TRUE, if curve has open end conditions, FALSE otherwise.     M
  83. *                                                                            *
  84. * KEYWORDS:                                                                  M
  85. *   BspCrvHasOpenEC, open end conditions                                     M
  86. *****************************************************************************/
  87. CagdBType BspCrvHasOpenEC(CagdCrvStruct *Crv)
  88. {
  89.     return BspKnotHasOpenEC(Crv -> KnotVector, Crv -> Length, Crv -> Order);
  90. }
  91.  
  92. /*****************************************************************************
  93. * DESCRIPTION:                                                               M
  94. * Returns TRUE iff the given Bspline surface has open end coditions.         M
  95. *                                                                            *
  96. * PARAMETERS:                                                                M
  97. *   Srf:      To check for open end conditions.                              M
  98. *                                                                            *
  99. * RETURN VALUE:                                                              M
  100. *   CagdBType:  TRUE, if surface has open end conditions, FALSE otherwise.   M
  101. *                                                                            *
  102. * KEYWORDS:                                                                  M
  103. *   BspSrfHasOpenEC, open end conditions                                     M
  104. *****************************************************************************/
  105. CagdBType BspSrfHasOpenEC(CagdSrfStruct *Srf)
  106. {
  107.     return
  108.     BspKnotHasOpenEC(Srf -> UKnotVector, Srf -> ULength, Srf -> UOrder) &&
  109.     BspKnotHasOpenEC(Srf -> VKnotVector, Srf -> VLength, Srf -> VOrder);
  110. }
  111.  
  112. /*****************************************************************************
  113. * DESCRIPTION:                                                               M
  114. * Returns TRUE iff the given Bspline surface has open end coditions in the   M
  115. * specified direction.                                 M
  116. *                                                                            *
  117. * PARAMETERS:                                                                M
  118. *   Srf:      To check for open end conditions.                              M
  119. *   Dir:      Either the U or the V parametric direction.                    M
  120. *                                                                            *
  121. * RETURN VALUE:                                                              M
  122. *   CagdBType:  TRUE, if surface has open end conditions, FALSE otherwise.   M
  123. *                                                                            *
  124. * KEYWORDS:                                                                  M
  125. *   BspSrfHasOpenECDir, open end conditions                                  M
  126. *****************************************************************************/
  127. CagdBType BspSrfHasOpenECDir(CagdSrfStruct *Srf, CagdSrfDirType Dir)
  128. {
  129.     switch (Dir) {
  130.     case CAGD_CONST_U_DIR:
  131.         return BspKnotHasOpenEC(Srf -> UKnotVector, Srf -> ULength,
  132.                     Srf -> UOrder);
  133.     case CAGD_CONST_V_DIR:
  134.         return BspKnotHasOpenEC(Srf -> VKnotVector, Srf -> VLength,
  135.                     Srf -> VOrder);
  136.     default:
  137.         CAGD_FATAL_ERROR(CAGD_ERR_DIR_NOT_CONST_UV);
  138.         return FALSE;
  139.     }
  140. }
  141.  
  142. /*****************************************************************************
  143. * DESCRIPTION:                                                               M
  144. * Returns TRUE iff the given knot vector has open end conditions.         M
  145. *                                                                            *
  146. * PARAMETERS:                                                                M
  147. *   KnotVector:   To check for open end condition.                           M
  148. *   Len:          Of knot vector.                                            M
  149. *   Order:        Of curve/surface the exploits this knot vector.            M
  150. *                                                                            *
  151. * RETURN VALUE:                                                              M
  152. *   CagdBType:     TRUE if KV has open end conditions.                       M
  153. *                                                                            *
  154. * KEYWORDS:                                                                  M
  155. *   BspKnotHasOpenEC, knot vectors, open end conditions                      M
  156. *****************************************************************************/
  157. CagdBType BspKnotHasOpenEC(CagdRType *KnotVector, int Len, int Order)
  158. {
  159.     int i,
  160.         LastIndex = Len + Order - 1;
  161.  
  162.     for (i = 1; i < Order; i++)
  163.        if (!APX_EQ_EPS(KnotVector[0], KnotVector[i], IRIT_EPSILON))
  164.         return FALSE;
  165.  
  166.     for (i = LastIndex - 1; i >= Len; i--)
  167.        if (!APX_EQ_EPS(KnotVector[LastIndex], KnotVector[i], IRIT_EPSILON))
  168.         return FALSE;
  169.  
  170.     return TRUE;
  171. }
  172.  
  173. /*****************************************************************************
  174. * DESCRIPTION:                                                               M
  175. * Returns TRUE iff t is in the parametric domain as define by the knot       M
  176. * vector KnotVector, its length Len, and the order Order.                 M
  177. *                                                                            *
  178. * PARAMETERS:                                                                M
  179. *   KnotVector:    To verify t is indeed in.                                 M
  180. *   Len:           Length of curve/surface using KnotVector. This is NOT the M
  181. *                  length of KnotVector which is equal to (Length + Order).  M
  182. *   Order:         Order of curve/surface using KnotVector.                  M
  183. *   Periodic:      TRUE if this KnotVector is periodic.                      M
  184. *   t:             Parametric value to verify.                               M
  185. *                                                                            *
  186. * RETURN VALUE:                                                              M
  187. *   CagdBType:    TRUE, if t is contained in the parametric domain, FALSE    M
  188. *                 otherwise.                                                 M
  189. *                                                                            *
  190. * KEYWORDS:                                                                  M
  191. *   BspKnotParamInDomain, parametric domain, knot vectors                    M
  192. *****************************************************************************/
  193. CagdBType BspKnotParamInDomain(CagdRType *KnotVector,
  194.                    int Len,
  195.                    int Order,
  196.                    CagdBType Periodic,
  197.                    CagdRType t)
  198. {
  199.     CagdRType
  200.     r1 = KnotVector[Order - 1],
  201.     r2 = KnotVector[Len + (Periodic ? Order - 1 : 0)];
  202.  
  203.     return (r1 < t || APX_EQ_EPS(r1, t, IRIT_EPSILON))
  204.         && (r2 > t || APX_EQ_EPS(r2, t, IRIT_EPSILON));
  205. }
  206.  
  207. /*****************************************************************************
  208. * DESCRIPTION:                                                               M
  209. * Returns the index of the last knot which is less than or equal to t in the M
  210. * given knot vector KnotVector of length Len. APX_EQ_EPS is used in equality.M
  211. *   Parameter t is assumed to be in the parametric domain for the knot       M
  212. * vector.                                     M
  213. *                                                                            *
  214. * PARAMETERS:                                                                M
  215. *   KnotVector:    To search for a knot with the LE relation to t.           M
  216. *   Len:           Of knot vector. This is not the length of the             M
  217. *                  curve/surface using this KnotVector.                      M
  218. *   t:             The parameter value to search for the LE relation.        M
  219. *                                                                            *
  220. * RETURN VALUE:                                                              M
  221. *   int:           Index of last knot in KnotVector that is LE t, or -1 if   M
  222. *                  t is below the first knot.                     M
  223. *                                                                            *
  224. * KEYWORDS:                                                                  M
  225. *   BspKnotLastIndexLE, knot vectors                                         M
  226. *****************************************************************************/
  227. int BspKnotLastIndexLE(CagdRType *KnotVector, int Len, CagdRType t)
  228. {
  229.     int i;
  230.  
  231.     for (i = 0;
  232.      i < Len && (KnotVector[i] <= t ||
  233.              APX_EQ_EPS(KnotVector[i], t, IRIT_EPSILON));
  234.      i++);
  235.  
  236.     return i - 1;
  237. }
  238.  
  239. /*****************************************************************************
  240. * DESCRIPTION:                                                               M
  241. * Returns the index of the last knot which is less t in the given knot       M
  242. * vector KnotVector of length Len. APX_EQ_EPS is used for equality.          M
  243. *   Parameter t is assumed to be in the parametric domain for the knot       M
  244. * vector.                                     M
  245. *                                                                            *
  246. * PARAMETERS:                                                                M
  247. *   KnotVector:    To search for a knot with the L relation to t.            M
  248. *   Len:           Of knot vector. This is not the length of the             M
  249. *                  curve/surface using this KnotVector.                      M
  250. *   t:             The parameter value to search for the L relation.         M
  251. *                                                                            *
  252. * RETURN VALUE:                                                              M
  253. *   int:           Index of last knot in KnotVector that is less than t or   M
  254. *                  -1 if t is below the first knot.                 M
  255. *                                                                            *
  256. * KEYWORDS:                                                                  M
  257. *   BspKnotLastIndexL, knot vectors                                          M
  258. *****************************************************************************/
  259. int BspKnotLastIndexL(CagdRType *KnotVector, int Len, CagdRType t)
  260. {
  261.     int i;
  262.  
  263.     for (i = 0;
  264.      i < Len &&
  265.      KnotVector[i] < t &&
  266.      !APX_EQ_EPS(KnotVector[i], t, IRIT_EPSILON);
  267.      i++);
  268.  
  269.     return i - 1;
  270. }
  271.  
  272. /*****************************************************************************
  273. * DESCRIPTION:                                                               M
  274. * Returns the index of the first knot which is greater than t in the given   M
  275. * knot vector KnotVector of length Len. APX_EQ_EPS is used for equality.     M
  276. *   Parameter t is assumed to be in the parametric domain for the knot       M
  277. * vector.                                     M
  278. *                                                                            *
  279. * PARAMETERS:                                                                M
  280. *   KnotVector:    To search for a knot with the G relation to t.            M
  281. *   Len:           Of knot vector. This is not the length of the             M
  282. *                  curve/surface using this KnotVector.                      M
  283. *   t:             The parameter value to search for the G relation.         M
  284. *                                                                            *
  285. * RETURN VALUE:                                                              M
  286. *   int:           Index of first knot in KnotVector that is greater than t  M
  287. *                  or Len if t is greater than last knot in KnotVector.      M
  288. *                                                                            *
  289. * KEYWORDS:                                                                  M
  290. *   BspKnotFirstIndexG, knot vectors                                         M
  291. *****************************************************************************/
  292. int BspKnotFirstIndexG(CagdRType *KnotVector, int Len, CagdRType t)
  293. {
  294.     int i;
  295.  
  296.     for (i = Len - 1;
  297.      i >= 0 &&
  298.      KnotVector[i] > t &&
  299.      !APX_EQ_EPS(KnotVector[i], t, IRIT_EPSILON);
  300.      i--);
  301.  
  302.     return i + 1;
  303. }
  304.  
  305. /*****************************************************************************
  306. * DESCRIPTION:                                                               M
  307. * Returns a uniform periodic knot vector for Len Control points and order    M
  308. * Order. The actual length of the KV is Len + Order + Order - 1.         M
  309. * If KnotVector is NULL it is being allocated dynamically.             M
  310. *                                                                            *
  311. * PARAMETERS:                                                                M
  312. *   Len:          Of control polygon/mesh of curve/surface that are to use   M
  313. *                 this knot vector.                                          M
  314. *   Order:        Of the curve/surface that are to use this knot vector.     M
  315. *   KnotVector:   If new knot vector is to be saved here, otherwise a new    M
  316. *                 space is allocated.                         M
  317. *                                                                            *
  318. * RETURN VALUE:                                                              M
  319. *   CagdRType *:  The created uniform periodic knot vector, either newly     M
  320. *                 allocated or given in Knotvector and just initialized.     M
  321. *                                                                            *
  322. * KEYWORDS:                                                                  M
  323. *   BspKnotUniformPeriodic, knot vectors, periodic end conditions, end       M
  324. *   conditions                                      M
  325. *****************************************************************************/
  326. CagdRType *BspKnotUniformPeriodic(int Len, int Order, CagdRType *KnotVector)
  327. {
  328.     int i,
  329.     KVLen = Len + Order + Order - 1;
  330.     CagdRType *KV;
  331.  
  332.     if (KnotVector == NULL)
  333.     KV = KnotVector = (CagdRType *) IritMalloc(sizeof(CagdRType) * KVLen);
  334.     else
  335.     KV = KnotVector;
  336.  
  337.     for (i = 0; i < KVLen; i++)
  338.     *KV++ = (CagdRType) i;
  339.  
  340.     return KnotVector;
  341. }
  342.  
  343. /*****************************************************************************
  344. * DESCRIPTION:                                                               M
  345. * Returns a uniform floating knot vector for Len Control points and order    M
  346. * Order. The actual length of the KV is Len + Order.                 M
  347. * If KnotVector is NULL it is being allocated dynamically.             M
  348. *                                                                            *
  349. * PARAMETERS:                                                                M
  350. *   Len:          Of control polygon/mesh of curve/surface that are to use   M
  351. *                 this knot vector.                                          M
  352. *   Order:        Of the curve/surface that are to use this knot vector.     M
  353. *   KnotVector:   If new knot vector is to be saved here, otherwise a new    M
  354. *                 space is allocated.                         M
  355. *                                                                            *
  356. * RETURN VALUE:                                                              M
  357. *   CagdRType *:  The created uniform floating knot vector, either newly     M
  358. *                 allocated or given in Knotvector and just initialized.     M
  359. *                                                                            *
  360. * KEYWORDS:                                                                  M
  361. *   BspKnotUniformFloat, knot vectors, floating end conditions, end          M
  362. *   conditions                                     M
  363. *****************************************************************************/
  364. CagdRType *BspKnotUniformFloat(int Len, int Order, CagdRType *KnotVector)
  365. {
  366.     int i;
  367.     CagdRType *KV;
  368.  
  369.     if (KnotVector == NULL)
  370.     KV = KnotVector = (CagdRType *) IritMalloc(sizeof(CagdRType) *
  371.                                 (Len + Order));
  372.     else
  373.     KV = KnotVector;
  374.  
  375.     for (i = 0; i < Len + Order; i++)
  376.     *KV++ = (CagdRType) i;
  377.  
  378.     return KnotVector;
  379. }
  380.  
  381. /*****************************************************************************
  382. * DESCRIPTION:                                                               M
  383. * Returns a uniform open knot vector for Len Control points and order        M
  384. * Order. The actual length of the KV is Len + Order.                 M
  385. * If KnotVector is NULL it is being allocated dynamically.             M
  386. *                                                                            *
  387. * PARAMETERS:                                                                M
  388. *   Len:          Of control polygon/mesh of curve/surface that are to use   M
  389. *                 this knot vector.                                          M
  390. *   Order:        Of the curve/surface that are to use this knot vector.     M
  391. *   KnotVector:   If new knot vector is to be saved here, otherwise a new    M
  392. *                 space is allocated.                         M
  393. *                                                                            *
  394. * RETURN VALUE:                                                              M
  395. *   CagdRType *:  The created uniform open knot vector, either newly         M
  396. *                 allocated or given in Knotvector and just initialized.     M
  397. *                                                                            *
  398. * KEYWORDS:                                                                  M
  399. *   BspKnotUniformOpen, knot vectors, open end conditions, end               M
  400. *   conditions                                      M
  401. *****************************************************************************/
  402. CagdRType *BspKnotUniformOpen(int Len, int Order, CagdRType *KnotVector)
  403. {
  404.     int i, j;
  405.     CagdRType *KV;
  406.  
  407.     if (KnotVector == NULL)
  408.     KV = KnotVector = (CagdRType *) IritMalloc(sizeof(CagdRType) *
  409.                                 (Len + Order));
  410.     else
  411.     KV = KnotVector;
  412.  
  413.     for (i = 0; i < Order; i++)
  414.     *KV++ = 0.0;
  415.     for (i = 1, j = Len - Order; i <= j; )
  416.     *KV++ = (CagdRType) i++;
  417.     for (j = 0; j < Order; j++)
  418.     *KV++ = (CagdRType) i;
  419.  
  420.     return KnotVector;
  421. }
  422.  
  423. /*****************************************************************************
  424. * DESCRIPTION:                                                               M
  425. * Applies an affine transformation to the given knot vector. Note affine     M
  426. * transformation on the knot vector does not change the Bspline curve.         M
  427. *   Knot vector is translated by Translate amount and scaled by Scale as     M
  428. *  KV[i] = (KV[i] - KV[0]) * Scale + (KV0 + Translate).                      V
  429. *   All transformation as taken place in place.                     M
  430. *                                                                            *
  431. * PARAMETERS:                                                                M
  432. *   KnotVector:     To affinely transform.                                   M
  433. *   Len:            Of knot vector. This is not the length of the curve or   M
  434. *                   surface using this knot vector.                          M
  435. *   Translate:      Amount to translate the knot vector.                     M
  436. *   Scale:          Amount to scale the knot vector.                         M
  437. *                                                                            *
  438. * RETURN VALUE:                                                              M
  439. *   void                                                                     M
  440. *                                                                            *
  441. * KEYWORDS:                                                                  M
  442. *   BspKnotAffineTrans, knot vectors, affine transformation                  M
  443. *****************************************************************************/
  444. void BspKnotAffineTrans(CagdRType *KnotVector,
  445.             int Len,
  446.             CagdRType Translate,
  447.             CagdRType Scale)
  448. {
  449.     int i;
  450.     CagdRType
  451.     KV0 = KnotVector[0];
  452.  
  453.     for (i = 0; i < Len; i++)
  454.     KnotVector[i] = (KnotVector[i] - KV0) * Scale + KV0 + Translate;
  455. }
  456.  
  457. /*****************************************************************************
  458. * DESCRIPTION:                                                               M
  459. * Applies an affine transformation to the given knot vector. Note affine     M
  460. * transformation on the knot vector does not change the Bspline curve.         M
  461. *   Knot vector is translated and scaled so as to span the domain from       M
  462. * MinVal top MaxVal. This works for open end condition curves only.         M
  463. *  KV[i] = (KV[i] - KV[0]) * Scale + MinVal,                                 V
  464. * where Scale = (MaxVal - MinVal) / (KV[Len - 1] - KV[0]).             M
  465. *   All transformation as taken place in place.                     M
  466. *                                                                            *
  467. * PARAMETERS:                                                                M
  468. *   KnotVector:     To affinely transform.                                   M
  469. *   Len:            Of knot vector. This is not the length of the curve or   M
  470. *                   surface using this knot vector.                          M
  471. *   MinVal, MaxVal: New parametric domain of knot vector.                    M
  472. *                                                                            *
  473. * RETURN VALUE:                                                              M
  474. *   void                                                                     M
  475. *                                                                            *
  476. * KEYWORDS:                                                                  M
  477. *   BspKnotAffineTrans2, knot vectors, affine transformation                 M
  478. *****************************************************************************/
  479. void BspKnotAffineTrans2(CagdRType *KnotVector,
  480.              int Len,
  481.              CagdRType MinVal,
  482.              CagdRType MaxVal)
  483. {
  484.     int i;
  485.     CagdRType
  486.     KV0 = KnotVector[0],
  487.     KVn = KnotVector[Len - 1],
  488.     Scale = (MaxVal - MinVal) / (KVn - KV0);
  489.  
  490.     for (i = 0; i < Len; i++)
  491.     KnotVector[i] = (KnotVector[i] - KV0) * Scale + MinVal;
  492. }
  493.  
  494. /*****************************************************************************
  495. * DESCRIPTION:                                                               M
  496. * Creates an identical copy of a given knot vector KnotVector of length Len. M
  497. *                                                                            *
  498. * PARAMETERS:                                                                M
  499. *   KnotVector:   Knot vector to duplicate                                   M
  500. *   Len:          Length of knot vector. This is not the length of the curve M
  501. *                 or surface using this knot vector.                         M
  502. *                                                                            *
  503. * RETURN VALUE:                                                              M
  504. *   CagdRType *:  The duplicated knot vector.                                M
  505. *                                                                            *
  506. * KEYWORDS:                                                                  M
  507. *   BspKnotCopy, allocation, knot vectors                                    M
  508. *****************************************************************************/
  509. CagdRType *BspKnotCopy(CagdRType *KnotVector, int Len)
  510. {
  511.     CagdRType
  512.     *NewKnotVector = (CagdRType *) IritMalloc(sizeof(CagdRType) * Len);
  513.  
  514.     CAGD_GEN_COPY(NewKnotVector, KnotVector, sizeof(CagdRType) * Len);
  515.  
  516.     return NewKnotVector;
  517. }
  518.  
  519. /*****************************************************************************
  520. * DESCRIPTION:                                                               M
  521. * Reverse a knot vector of length Len.    Reversing of knot vector keeps the   M
  522. * knots monotonically non-decreasing as well as the parametric domain. Only  M
  523. * the spaces between the knots are being flipped. For example the knot       M
  524. * vector:                                                                    M
  525. *                        [0 0 0 0 1 2 2 6 6 6 6]                             V
  526. * is reversed to be:                                                         M
  527. *                        [0 0 0 0 4 4 5 6 6 6 6]                             V
  528. *                                                                            *
  529. * PARAMETERS:                                                                M
  530. *   KnotVector:   Knot vector to be reversed.                                M
  531. *   Len:          Length of knot vector. This is not the length of the curve M
  532. *                 or surface using this knot vector.                         M
  533. *                                                                            *
  534. * RETURN VALUE:                                                              M
  535. *   CagdRType *:  The reversed knot vector.                                  M
  536. *                                                                            *
  537. * KEYWORDS:                                                                  M
  538. *   BspKnotReverse, knot vectors, reverse                                    M
  539. *****************************************************************************/
  540. CagdRType *BspKnotReverse(CagdRType *KnotVector, int Len)
  541. {
  542.     int i;
  543.     CagdRType
  544.     *NewKnotVector = (CagdRType *) IritMalloc(sizeof(CagdRType) * Len),
  545.     t = KnotVector[Len - 1] + KnotVector[0];
  546.  
  547.     for (i = 0; i < Len; i++)
  548.     NewKnotVector[i] = t - KnotVector[Len - i - 1];
  549.  
  550.     return NewKnotVector;
  551. }
  552.  
  553. /*****************************************************************************
  554. * DESCRIPTION:                                                               M
  555. * Returns a knot vector that contains all the knots in KnotVector1 that are  M
  556. * not in KnotVector2.                                 M
  557. *   NewLen is set to new KnotVector length.                     M
  558. *                                                                            *
  559. * PARAMETERS:                                                                M
  560. *   KnotVector1:   First  knot vector.                                       M
  561. *   Len1:          Length of KnotVector1. This is not the length of the      M
  562. *                  curve or surface using this knot vector.                  M
  563. *   KnotVector2:   Second knot vector.                                       M
  564. *   Len1:          Length of KnotVector2. This is not the length of the      M
  565. *                  curve or surface using this knot vector.                  M
  566. *   NewLen:        To save the size of the knot vector that contains the     M
  567. *                  computed subset of KnotVector1 / KnotVector2.             M
  568. *                                                                            *
  569. * RETURN VALUE:                                                              M
  570. *   CagdRType *:   The subset of knot in KnotVector1 that are not in         M
  571. *                  KnotVector2 (KnotVector1 / KnotVector2).                  M
  572. *                                                                            *
  573. * KEYWORDS:                                                                  M
  574. *   BspKnotSubtrTwo, knot vectors, compatibility, refinement                 M
  575. *****************************************************************************/
  576. CagdRType *BspKnotSubtrTwo(CagdRType *KnotVector1,
  577.                int Len1,
  578.                CagdRType *KnotVector2,
  579.                int Len2,
  580.                int *NewLen)
  581. {
  582.     int i = 0,
  583.     j = 0;
  584.     CagdRType
  585.     *NewKnotVector = (CagdRType *) IritMalloc(sizeof(CagdRType) * Len1),
  586.     *t = NewKnotVector;
  587.  
  588.     *NewLen = 0;
  589.     while (i < Len1 && j < Len2) {
  590.     if (APX_EQ_EPS(KnotVector1[i], KnotVector2[j], IRIT_EPSILON)) {
  591.         i++;
  592.         j++;
  593.     }
  594.     else if (KnotVector1[i] > KnotVector2[j]) {
  595.         j++;
  596.     }
  597.     else {
  598.         /* Current KnotVector1 value is less than current KnotVector2: */
  599.         *t++ = KnotVector1[i++];
  600.         (*NewLen)++;
  601.     }
  602.     }
  603.  
  604.     return NewKnotVector;
  605. }
  606.  
  607. /*****************************************************************************
  608. * DESCRIPTION:                                                               M
  609. * Merges two knot vector KnotVector1 and KnotVector2 of length Len1 and Len2 M
  610. * respectively into one. If Mult is not zero then knot multiplicity is       M
  611. * tested not to be larger than Mult value.                     M
  612. *   NewLen is set to new KnotVector length.                                  M
  613. *                                                                            *
  614. * PARAMETERS:                                                                M
  615. *   KnotVector1:   First  knot vector.                                       M
  616. *   Len1:          Length of KnotVector1. This is not the length of the      M
  617. *                  curve or surface using this knot vector.                  M
  618. *   KnotVector2:   Second knot vector.                                       M
  619. *   Len2:          Length of KnotVector2. This is not the length of the      M
  620. *                  curve or surface using this knot vector.                  M
  621. *   Mult:          Maximum multiplicity to allow in merged knot vector.      M
  622. *   NewLen:        To save the size of the knot vector that contains the     M
  623. *                  merged knot vectors.                             M
  624. *                                                                            *
  625. * RETURN VALUE:                                                              M
  626. *   CagdRType *:   The merged knot verctor (KnotVector1 U KnotVector2).      M
  627. *                                                                            *
  628. * KEYWORDS:                                                                  M
  629. *   BspKnotMergeTwo, knot vectors, compatibility, refinement                 M
  630. *****************************************************************************/
  631. CagdRType *BspKnotMergeTwo(CagdRType *KnotVector1,
  632.                int Len1,
  633.                CagdRType *KnotVector2,
  634.                int Len2,
  635.                int Mult,
  636.                int *NewLen)
  637. {
  638.     int i = 0,
  639.     j = 0,
  640.     k = 0,
  641.         m = 0,
  642.     Len = Len1 + Len2;
  643.     CagdRType t,
  644.     *NewKnotVector = (CagdRType *) IritMalloc(sizeof(CagdRType) * Len);
  645.  
  646.     if (Mult == 0)
  647.     Mult = Len + 1;
  648.  
  649.     while (i < Len1 && j < Len2) {
  650.     if (KnotVector1[i] < KnotVector2[j]) {
  651.         /* Use value from KnotVector1: */
  652.         t = KnotVector1[i++];
  653.     }
  654.     else {
  655.         /* Use value from KnotVector2: */
  656.         t = KnotVector2[j++];
  657.     }
  658.  
  659.     if (k == 0 || (k > 0 &&
  660.                !APX_EQ_EPS(NewKnotVector[k - 1], t, IRIT_EPSILON))) {
  661.         NewKnotVector[k++] = t;
  662.         m = 1;
  663.     }
  664.     else if (m < Mult) {
  665.         NewKnotVector[k++] = t;
  666.         m++;
  667.     }
  668.     }
  669.  
  670.     while (i < Len1)
  671.     NewKnotVector[k++] = KnotVector1[i++];
  672.     while (j < Len2)
  673.     NewKnotVector[k++] = KnotVector1[j++];
  674.  
  675.     /* It should be noted that k <= Len so there is a chance some of the new */
  676.     /* KnotVector space will not be used (it is not memory leak!). If you    */
  677.     /* really care that much - copy it to a new allocated vector of size k   */
  678.     /* and return it while freeing the original of size Len.             */
  679.     *NewLen = k;
  680.  
  681.     return NewKnotVector;
  682. }
  683.  
  684. /*****************************************************************************
  685. * DESCRIPTION:                                                               M
  686. * Merges two knot vector KnotVector1 and KnotVector2 of length Len1 and Len2 M
  687. * respectively into one, from geometries of orders Order1 and Order2.         M
  688. *   Merged knot vector is for order ResOrder so that the resulting curve can M
  689. * represent the discontinuities in both geometries.                     M
  690. *   Assumes both knot vectors are open end spanning the same domain.         M
  691. *                                                                            *
  692. * PARAMETERS:                                                                M
  693. *   KnotVector1:   First  knot vector.                                       M
  694. *   Len1:          Length of KnotVector1. This is not the length of the      M
  695. *                  curve or surface using this knot vector.                  M
  696. *   Order1:        Order of first knot vector's geometry.                    M
  697. *   KnotVector2:   Second knot vector.                                       M
  698. *   Len2:          Length of KnotVector2. This is not the length of the      M
  699. *                  curve or surface using this knot vector.                  M
  700. *   Order2:        Order of secon knot vector's geometry.                    M
  701. *   ResOrder:      Expected order of geometry that will use the merged       M
  702. *                  knot vector.                                              M
  703. *   NewLen:        To save the size of the knot vector that contains the     M
  704. *                  merged knot vectors.                             M
  705. *                                                                            *
  706. * RETURN VALUE:                                                              M
  707. *   CagdRType *:   The merged knot verctor (KnotVector1 U KnotVector2).      M
  708. *                                                                            *
  709. * KEYWORDS:                                                                  M
  710. *   BspKnotContinuityMergeTwo, knot vectors, compatibility, refinement       M
  711. *****************************************************************************/
  712. CagdRType *BspKnotContinuityMergeTwo(CagdRType *KnotVector1,
  713.                      int Len1,
  714.                      int Order1,
  715.                      CagdRType *KnotVector2,
  716.                      int Len2,
  717.                      int Order2,
  718.                      int ResOrder,
  719.                      int *NewLen)
  720. {
  721.     int l1, l2, m, cont,
  722.     i = 0,
  723.     j = 0,
  724.     k = 0,
  725.     Len = (Len1 + Len2) * (1 + ResOrder - MAX(Order1, Order2));
  726.     CagdRType t,
  727.     *NewKnotVector = (CagdRType *) IritMalloc(sizeof(CagdRType) * Len);
  728.  
  729.     while (i < Len1 && j < Len2) {
  730.     if (APX_EQ_EPS(KnotVector1[i], KnotVector2[j], IRIT_EPSILON)) {
  731.         /* Compute multiplicity and continuity. */
  732.         for (l1 = 1;
  733.          i + l1 < Len1 &&
  734.          APX_EQ_EPS(KnotVector1[i], KnotVector1[i + l1], IRIT_EPSILON);
  735.          l1++);
  736.         for (l2 = 1;
  737.          j + l2 < Len2 &&
  738.          APX_EQ_EPS(KnotVector2[j], KnotVector2[j + l2], IRIT_EPSILON);
  739.          l2++);
  740.         cont = MIN(Order1 - l1, Order2 - l2) - 1;
  741.  
  742.         /* Use value from KnotVector1: */
  743.         t = KnotVector1[i];
  744.         i += l1;
  745.         j += l2;
  746.     }
  747.     else if (KnotVector1[i] < KnotVector2[j]) {
  748.         /* Compute multiplicity and continuity. */
  749.         for (l1 = 1;
  750.          i + l1 < Len1 &&
  751.          APX_EQ_EPS(KnotVector1[i], KnotVector1[i + l1], IRIT_EPSILON);
  752.          l1++);
  753.         cont = Order1 - l1 - 1;
  754.  
  755.         /* Use value from KnotVector1: */
  756.         t = KnotVector1[i];
  757.         i += l1;
  758.     }
  759.     else {
  760.         /* Compute multiplicity and continuity. */
  761.         for (l2 = 1;
  762.          j + l2 < Len2 &&
  763.          APX_EQ_EPS(KnotVector2[j], KnotVector2[j + l2], IRIT_EPSILON);
  764.          l2++);
  765.         cont = Order2 - l2 - 1;
  766.  
  767.         /* Use value from KnotVector2: */
  768.         t = KnotVector2[j++];
  769.         j += l2;
  770.     }
  771.  
  772.     for (m = 0; m < ResOrder - cont - 1; m++)
  773.         NewKnotVector[k++] = t;
  774.     }
  775.  
  776.     /* It should be noted that k <= Len so there is a chance some of the new */
  777.     /* KnotVector space will not be used (it is not memory leak!). If you    */
  778.     /* really care that much - copy it to a new allocated vector of size k   */
  779.     /* and return it while freeing the original of size Len.             */
  780.     *NewLen = k;
  781.  
  782.     return NewKnotVector;
  783. }
  784.  
  785. /*****************************************************************************
  786. * DESCRIPTION:                                                               M
  787. * Creates a new knot vector from the given KnotVector that averages Ave         M
  788. * consequetive knots.                                 M
  789. *  Resulting vector will have (Len - Ave + 1) elements.                 M
  790. *  See also BspKnotNodes.                             M
  791. *                                                                            *
  792. * PARAMETERS:                                                                M
  793. *   KnotVector:    To average out.                                           M
  794. *   Len:           Length of KnotVector. This is not the length of the       M
  795. *                  curve or surface using this knot vector.                  M
  796. *   Ave:           How many knots to average each time.                      M
  797. *                                                                            *
  798. * RETURN VALUE:                                                              M
  799. *   CagdRType *:   The averaged knot vector of length (Len - Ave + 1).       M
  800. *                                                                            *
  801. * KEYWORDS:                                                                  M
  802. *   BspKnotAverage, knot vectors, node values                                M
  803. *****************************************************************************/
  804. CagdRType *BspKnotAverage(CagdRType *KnotVector, int Len, int Ave)
  805. {
  806.     int i,
  807.     AveLen = Len - Ave + 1;
  808.     CagdRType
  809.     *AveVector = (CagdRType *) IritMalloc(sizeof(CagdRType) * AveLen);
  810.  
  811.     if (Ave > Len || Ave < 1)
  812.     CAGD_FATAL_ERROR(CAGD_ERR_OUT_OF_RANGE);
  813.  
  814.     /* Compute the first average value. */
  815.     for (AveVector[0] = 0.0, i = 0; i < Ave; i++)
  816.     AveVector[0] += KnotVector[i];
  817.  
  818.     for (i = 1; i < AveLen; i++)
  819.     AveVector[i] = AveVector[i - 1] + KnotVector[i + Ave - 1]
  820.                     - KnotVector[i - 1];
  821.  
  822.     for (i = 0; i < AveLen; i++)
  823.     AveVector[i] /= Ave;
  824.  
  825.     return AveVector;
  826. }
  827.  
  828. /******************************************************************************
  829. * DESCRIPTION:                                                               M
  830. * Creates a new vector with the given KnotVector Node values.             M
  831. *   The nodes are the approximated parametric value associated with the each M
  832. * control point. Therefore for a knot vector of length Len and order Order   M
  833. * there are Len - Order control points and therefore nodes.             M
  834. *   Nodes are defined as (k = Order - 1 or degree):                 M
  835. *                                             M
  836. *      i+k                                     V
  837. *       -                 First Node N(i = 0)             V
  838. *       \                                     V
  839. *          / KnotVector(j)        Last Node  N(i = Len - k - 2)         V
  840. *       -                                     V
  841. *        j=i+1                                     V
  842. * N(i) = -----------------                             V
  843. *            k                                 V
  844. *                                             M
  845. *  See also BspKnotAverage.                             M
  846. *                                                                            *
  847. * PARAMETERS:                                                                M
  848. *   KnotVector:    To average out as nodes.                                  M
  849. *   Len:           Length of KnotVector. This is not the length of the       M
  850. *                  curve or surface using this knot vector.                  M
  851. *   Order:         Of curve or surface that exploits this knot vector.       M
  852. *                                                                            *
  853. * RETURN VALUE:                                                              M
  854. *   CagdRType *:   The nodes computed for the given knot vector.             M
  855. *                                                                            *
  856. * KEYWORDS:                                                                  M
  857. *   BspKnotNodes, knot vectors, node values                                  M
  858. *****************************************************************************/
  859. CagdRType *BspKnotNodes(CagdRType *KnotVector, int Len, int Order)
  860. {
  861.     int i, j,
  862.     k = MAX(Order - 1, 1),
  863.     NodeLen = Len - Order;
  864.     CagdRType
  865.     TMin = KnotVector[k],
  866.     TMax = KnotVector[NodeLen],
  867.     *NodeVector = (CagdRType *) IritMalloc(sizeof(CagdRType) * NodeLen);
  868.  
  869.     for (i = 0; i < NodeLen; i++) {
  870.     NodeVector[i] = 0.0;
  871.     for (j = i + 1; j <= i + k; j++)
  872.         NodeVector[i] += BOUND(KnotVector[j], TMin, TMax);
  873.     NodeVector[i] /= k;
  874.     }
  875.  
  876.     return NodeVector;
  877. }
  878.  
  879. /*****************************************************************************
  880. * DESCRIPTION:                                                               M
  881. * Returns the nodes of a freeform curve.                     M
  882. *                                                                            *
  883. * PARAMETERS:                                                                M
  884. *   Crv:      To compute node values for.                                    M
  885. *                                                                            *
  886. * RETURN VALUE:                                                              M
  887. *   CagdRType *: Node values of the given curve.                             M
  888. *                                                                            *
  889. * KEYWORDS:                                                                  M
  890. *   CagdCrvNodes, node values                                                M
  891. *****************************************************************************/
  892. CagdRType *CagdCrvNodes(CagdCrvStruct *Crv)
  893. {
  894.     int i,
  895.         Order = Crv -> Order,
  896.     Length = CAGD_CRV_PT_LST_LEN(Crv);
  897.     CagdRType *NodeVector;
  898.  
  899.     switch (Crv -> GType) {
  900.     case CAGD_CBEZIER_TYPE:
  901.         NodeVector = (CagdRType *) IritMalloc(sizeof(CagdRType) * Order);
  902.         for (i = 0; i < Order; i++)
  903.             NodeVector[i] = i / ((RealType) (Order - 1));
  904.         break;
  905.     case CAGD_CBSPLINE_TYPE:
  906.         NodeVector = BspKnotNodes(Crv -> KnotVector, Length + Order, Order);
  907.         break;
  908.     default:
  909.         NodeVector = NULL;
  910.         break;
  911.     }
  912.  
  913.     return NodeVector;
  914. }
  915.  
  916. /*****************************************************************************
  917. * DESCRIPTION:                                                               M
  918. * Returns the nodes of a freeform surface.                     M
  919. *                                                                            *
  920. * PARAMETERS:                                                                M
  921. *   Srf:      To compute node values for.                                    M
  922. *   Dir:      Either the U or the V parametric direction.                    M
  923. *                                                                            *
  924. * RETURN VALUE:                                                              M
  925. *   CagdRType *: Node values of the given surface and given parametric       M
  926. *                direction.                                                  M
  927. *                                                                            *
  928. * KEYWORDS:                                                                  M
  929. *   CagdSrfNodes, node values                                                M
  930. *****************************************************************************/
  931. CagdRType *CagdSrfNodes(CagdSrfStruct *Srf, CagdSrfDirType Dir)
  932. {
  933.     int i,
  934.         Order = Dir == CAGD_CONST_U_DIR ? Srf -> UOrder : Srf -> VOrder,
  935.     Length = Dir == CAGD_CONST_U_DIR ? Srf -> ULength : Srf -> VLength;
  936.     CagdRType *NodeVector;
  937.  
  938.     if (Dir != CAGD_CONST_U_DIR && Dir != CAGD_CONST_V_DIR) {
  939.         CAGD_FATAL_ERROR(CAGD_ERR_DIR_NOT_CONST_UV);
  940.     return NULL;
  941.     }
  942.  
  943.     switch (Srf -> GType) {
  944.     case CAGD_SBEZIER_TYPE:
  945.         NodeVector = (CagdRType *) IritMalloc(sizeof(CagdRType) * Order);
  946.         for (i = 0; i < Order; i++)
  947.             NodeVector[i] = i / ((RealType) (Order - 1));
  948.         break;
  949.     case CAGD_SBSPLINE_TYPE:
  950.         NodeVector = BspKnotNodes(Dir == CAGD_CONST_U_DIR ?
  951.                           Srf -> UKnotVector :
  952.                           Srf -> VKnotVector,
  953.                       Length + Order, Order);
  954.         break;
  955.     default:
  956.         NodeVector = NULL;
  957.         break;
  958.     }
  959.  
  960.     return NodeVector;
  961. }
  962.  
  963. /*****************************************************************************
  964. * DESCRIPTION:                                                               M
  965. * Finds the parameter value with the largest coefficient of the curve using  M
  966. * nodes values to estimate the coefficients' parameters.             M
  967. *                                                                            *
  968. * PARAMETERS:                                                                M
  969. *   Crv:           To compute the parameter node value of the largest        M
  970. *                  coefficient.                                              M
  971. *   Axis:          Which axis should we search for maximal coefficient?      M
  972. *                  1 for X, 2 for Y, etc.                                    M
  973. *   MaxVal:        The coefficient itself will be place herein.              M
  974. *                                                                            *
  975. * RETURN VALUE:                                                              M
  976. *   CagdRType:     The node parameter value of the detected maximal          M
  977. *                  coefficient.                             M
  978. *                                                                            *
  979. * KEYWORDS:                                                                  M
  980. *   BspCrvMaxCoefParam, extremum                                             M
  981. *****************************************************************************/
  982. CagdRType BspCrvMaxCoefParam(CagdCrvStruct *Crv, int Axis, CagdRType *MaxVal)
  983. {
  984.     int i,
  985.     Index = 0,
  986.     Length = Crv -> Length,
  987.     Order = Crv -> Order;
  988.     CagdRType
  989.     *Points = Crv -> Points[Axis],
  990.     R = *Points,
  991.         *Nodes = BspKnotNodes(Crv -> KnotVector, Length + Order, Order);
  992.  
  993.     for (i = 0; i < Length; i++, Points++) {
  994.     if (*Points > R) {
  995.         R = *Points;
  996.         Index = i;
  997.     }
  998.     }
  999.     *MaxVal = R;
  1000.  
  1001.     R = Nodes[Index];
  1002.     IritFree(Nodes);
  1003.  
  1004.     return R;
  1005. }
  1006.  
  1007. /*****************************************************************************
  1008. * DESCRIPTION:                                                               M
  1009. * Finds the parameter value with the largest coefficient of the surface      M
  1010. * using nodes values to estimate the coefficients' parameters.             M
  1011. * Returns a pointer to a static array of two elements holding U and V.         M
  1012. *                                                                            *
  1013. * PARAMETERS:                                                                M
  1014. *   Srf:           To compute the parameter node value of the largest        M
  1015. *                  coefficient.                                              M
  1016. *   Axis:          Which axis should we search for maximal coefficient?      M
  1017. *                  1 for X, 2 for Y, etc.                                    M
  1018. *   MaxVal:        The coefficient itself will be place herein.              M
  1019. *                                                                            *
  1020. * RETURN VALUE:                                                              M
  1021. *   CagdRType *:   The node UV parameter values of the detected maximal      M
  1022. *                  coefficient.                             M
  1023. *                                                                            *
  1024. * KEYWORDS:                                                                  M
  1025. *   BspSrfMaxCoefParam, extremum                                             M
  1026. *****************************************************************************/
  1027. CagdRType *BspSrfMaxCoefParam(CagdSrfStruct *Srf, int Axis, CagdRType *MaxVal)
  1028. {
  1029.     static CagdRType UV[2];
  1030.     int i,
  1031.     UIndex = 0,
  1032.     VIndex = 0,
  1033.     ULength = Srf -> ULength,
  1034.     VLength = Srf -> VLength,
  1035.     UOrder = Srf -> UOrder,
  1036.     VOrder = Srf -> VOrder;
  1037.     CagdRType
  1038.     *Points = Srf -> Points[Axis],
  1039.     R = *Points,
  1040.         *UNodes = BspKnotNodes(Srf -> UKnotVector, ULength + UOrder, UOrder),
  1041.         *VNodes = BspKnotNodes(Srf -> VKnotVector, VLength + VOrder, VOrder);
  1042.  
  1043.     for (i = 0; i < ULength * VLength; i++, Points++) {
  1044.     if (*Points > R) {
  1045.         R = *Points;
  1046.         UIndex = i % ULength;
  1047.         VIndex = i / ULength;
  1048.     }
  1049.     }
  1050.     *MaxVal = R;
  1051.  
  1052.     UV[0] = UNodes[UIndex];
  1053.     UV[1] = VNodes[VIndex];
  1054.     IritFree(UNodes);
  1055.     IritFree(VNodes);
  1056.     return UV;
  1057. }
  1058.  
  1059. /*****************************************************************************
  1060. * DESCRIPTION:                                                               M
  1061. *   Creates a new vector with t inserted as a new knot. Attempt is made to   M
  1062. * make sure t is in the knot vector domain.                     M
  1063. *   No test is made for the current multiplicity of knot t in KnotVector.    M
  1064. *   This function only constructs a refined knot vector and does not         M
  1065. * compute the actual refined coefficients.                                   M
  1066. *                                                                            *
  1067. * PARAMETERS:                                                                M
  1068. *   KnotVector:    To insert new knot t in.                                  M
  1069. *   Order:         Of geometry that exploits KnotVector.                     M
  1070. *   Len:           Length of curve/surface using KnotVector. This is NOT the M
  1071. *                  length of KnotVector which is equal to (Length + Order).  M
  1072. *   t:             The new knot t to insert.                                 M
  1073. *                                                                            *
  1074. * RETURN VALUE:                                                              M
  1075. *   CagdRType *:   A new knot vector larger by one than KnotVector that      M
  1076. *                  contains t.                                               M
  1077. *                                                                            *
  1078. * KEYWORDS:                                                                  M
  1079. *   BspKnotInsertOne, knot vectors, knot insertion, refinement               M
  1080. *****************************************************************************/
  1081. CagdRType *BspKnotInsertOne(CagdRType *KnotVector,
  1082.                 int Order,
  1083.                 int Len,
  1084.                 CagdRType t)
  1085. {
  1086.     int Mult = BspKnotFindMult(KnotVector, Order, Len, t) + 1;
  1087.  
  1088.     return BspKnotInsertMult(KnotVector, Order, &Len, t, Mult);
  1089. }
  1090.  
  1091. /*****************************************************************************
  1092. * DESCRIPTION:                                                               M
  1093. * Inserts Mult knots with value t into the knot vector KnotVector.         M
  1094. *   Attempt is made to make sure t in knot vector domain.             M
  1095. *   If a knot equal to t (up to APX_EQ) already exists with multiplicity i   M
  1096. * only (Mult - i) knot are being inserted into the new knot vector.         M
  1097. *   Len is updated to the resulting knot vector.                 M
  1098. *   It is possible to DELETE a knot using this routine by specifying         M
  1099. * multiplicity less then current multiplicity!                     M
  1100. *   This function only constructs a refined knot vector and does not         M
  1101. * compute the actual refined coefficients.                                   M
  1102. *                                                                            *
  1103. * PARAMETERS:                                                                M
  1104. *   KnotVector:    To insert new knot t in.                                  M
  1105. *   Order:         Of geometry that exploits KnotVector.                     M
  1106. *   Len:           Length of curve/surface using KnotVector. This is NOT the M
  1107. *                  length of KnotVector which is equal to (Length + Order).  M
  1108. *   t:             The new knot t to insert.                                 M
  1109. *   Mult:          The multiplicity that this knot should have in resulting  M
  1110. *                  knot vector.                             M
  1111. *                                                                            *
  1112. * RETURN VALUE:                                                              M
  1113. *   CagdRType *:   A new knot vector derived from KnotVector that has        M
  1114. *                  a mltiplicity of exacly Mult at the knot t.               M
  1115. *                                                                            *
  1116. * KEYWORDS:                                                                  M
  1117. *   BspKnotInsertMult, knot vectors, knot insertion, refinement              M
  1118. *****************************************************************************/
  1119. CagdRType *BspKnotInsertMult(CagdRType *KnotVector,
  1120.                  int Order,
  1121.                  int *Len,
  1122.                  CagdRType t,
  1123.                  int Mult)
  1124. {
  1125.     int i, CurrentMult, NewLen, FirstIndex;
  1126.     CagdRType *NewKnotVector;
  1127.  
  1128.     if (!BspKnotParamInDomain(KnotVector, *Len, Order, FALSE, t))
  1129.     CAGD_FATAL_ERROR(CAGD_ERR_T_NOT_IN_CRV);
  1130.  
  1131.     CurrentMult = BspKnotFindMult(KnotVector, Order, *Len, t);
  1132.     NewLen = *Len + Mult - CurrentMult;
  1133.     NewKnotVector = (CagdRType *) IritMalloc(sizeof(CagdRType) *
  1134.                                 (NewLen + Order));
  1135.     FirstIndex = BspKnotLastIndexL(KnotVector, *Len + Order, t) + 1;
  1136.  
  1137.     /* Copy all the knot before the knot t. */
  1138.     CAGD_GEN_COPY(NewKnotVector, KnotVector, sizeof(CagdRType) * FirstIndex);
  1139.  
  1140.     /* Insert Mult knot of value t. */
  1141.     for (i = FirstIndex; i < FirstIndex + Mult; i++)
  1142.     NewKnotVector[i] = t;
  1143.  
  1144.     /* And copy the second part. */
  1145.     CAGD_GEN_COPY(&NewKnotVector[FirstIndex + Mult],
  1146.           &KnotVector[FirstIndex + CurrentMult],
  1147.           sizeof(CagdRType) * (*Len + Order - FirstIndex - Mult + 1));
  1148.  
  1149.     *Len = NewLen;
  1150.     return NewKnotVector;
  1151. }
  1152.  
  1153. /*****************************************************************************
  1154. * DESCRIPTION:                                                               M
  1155. * Returns the multiplicity of knot t in knot vector KnotVector, zero if      M
  1156. * none.                                                                      M
  1157. *                                                                            *
  1158. * PARAMETERS:                                                                M
  1159. *   KnotVector:    To test multiplicity of knot value t at.                  M
  1160. *   Order:         Of geometry that exploits KnotVector.                     M
  1161. *   Len:           Length of curve/surface using KnotVector. This is NOT the M
  1162. *                  length of KnotVector which is equal to (Length + Order).  M
  1163. *   t:             The knot to verify the multiplicity of.                   M
  1164. *                                                                            *
  1165. * RETURN VALUE:                                                              M
  1166. *   int:           Multiplicity of t in KnotVector.                          M
  1167. *                                                                            *
  1168. * KEYWORDS:                                                                  M
  1169. *   BspKnotFindMult, knot vectors                                            M
  1170. *****************************************************************************/
  1171. int BspKnotFindMult(CagdRType *KnotVector, int Order, int Len, CagdRType t)
  1172. {
  1173.     int LastIndex, FirstIndex;
  1174.  
  1175.     if (!BspKnotParamInDomain(KnotVector, Len, Order, FALSE, t))
  1176.     CAGD_FATAL_ERROR(CAGD_ERR_T_NOT_IN_CRV);
  1177.  
  1178.     FirstIndex = BspKnotLastIndexL(KnotVector, Len, t) + 1;
  1179.  
  1180.     for (LastIndex = FirstIndex;
  1181.      LastIndex < Len && APX_EQ_EPS(KnotVector[LastIndex], t, IRIT_EPSILON);
  1182.      LastIndex++);
  1183.  
  1184.     return LastIndex - FirstIndex;
  1185. }
  1186.  
  1187. /*****************************************************************************
  1188. * DESCRIPTION:                                                               M
  1189. * Scans the given knot vector to a potential C1 discontinuity.             M
  1190. *   Returns TRUE if found one and set t to its parameter value.             M
  1191. *   Assumes knot vector has open end condition.                     M
  1192. *   A knot vector with multiplicity of a knot of (Order - 1) can be C1       M
  1193. * discontinuous at that knot. However, this is only a necessary condition    M
  1194. * for C1 discontinuity in the geometry.                                      M
  1195. *                                                                            *
  1196. * PARAMETERS:                                                                M
  1197. *   KnotVector:    To test for potential C1 dicontinuities.                  M
  1198. *   Order:         Of geometry that exploits KnotVector.                     M
  1199. *   Length:        Length of curve/surface using KnotVector. This is NOT the M
  1200. *                  length of KnotVector which is equal to (Length + Order).  M
  1201. *   t:             Where to put the parameter value (knot) that can be C2    M
  1202. *                  discontinuous.                                            M
  1203. *                                                                            *
  1204. * RETURN VALUE:                                                              M
  1205. *   CagdBType:     TRUE if found a potential C1 discontinuity, FALSE         M
  1206. *           otherwise.                             M
  1207. *                                                                            *
  1208. * KEYWORDS:                                                                  M
  1209. *   BspKnotC1Discont, knot vectors, continuity, discontinuity                M
  1210. *****************************************************************************/
  1211. CagdBType BspKnotC1Discont(CagdRType *KnotVector,
  1212.                int Order,
  1213.                int Length,
  1214.                CagdRType *t)
  1215. {
  1216.     int i, Count;
  1217.     CagdRType
  1218.     LastT = KnotVector[0] - 1.0;
  1219.  
  1220.     for (i = Order, Count = 0; i < Length; i++) {
  1221.     if (APX_EQ_EPS(LastT, KnotVector[i], IRIT_EPSILON))
  1222.         Count++;
  1223.     else {
  1224.         Count = 1;
  1225.         LastT = KnotVector[i];
  1226.     }
  1227.  
  1228.     if (Count >= Order - 1) {
  1229.         *t = LastT;
  1230.         return TRUE;
  1231.     }
  1232.     }
  1233.  
  1234.     return FALSE;
  1235. }
  1236.  
  1237. /*****************************************************************************
  1238. * DESCRIPTION:                                                               M
  1239. * Scans the given knot vector for all potential C1 discontinuity. Returns    M
  1240. * a vector holding the parameter values of the potential C1 discontinuities, M
  1241. * NULL of none found.                                 M
  1242. *   Sets n to length of returned vector.                     M
  1243. *   Assumes knot vector has open end condition.                     M
  1244. *   A knot vector with multiplicity of a knot of (Order - 1) can be C1       M
  1245. * discontinuous at that knot. However, this is only a necessary condition    M
  1246. * for C1 discontinuity in the geometry.                                      M
  1247. *                                                                            *
  1248. * PARAMETERS:                                                                M
  1249. *   KnotVector:    To test for potential C1 dicontinuities.                  M
  1250. *   Order:         Of geometry that exploits KnotVector.                     M
  1251. *   Length:        Length of curve/surface using KnotVector. This is NOT the M
  1252. *                  length of KnotVector which is equal to (Length + Order).  M
  1253. *   n:             Length of returned vector - number of potential C1        M
  1254. *                  discontinuities found.                                    M
  1255. *                                                                            *
  1256. * RETURN VALUE:                                                              M
  1257. *   CagdRType *:   Vector holding all parametr values with potential C1      M
  1258. *                  discontinuities.                                          M
  1259. *                                                                            *
  1260. * KEYWORDS:                                                                  M
  1261. *   BspKnotAllC1Discont, knot vectors, continuity, discontinuity             M
  1262. *****************************************************************************/
  1263. CagdRType *BspKnotAllC1Discont(CagdRType *KnotVector,
  1264.                    int Order,
  1265.                    int Length,
  1266.                    int *n)
  1267. {
  1268.     int i, Count,
  1269.     C1DiscontCount = 0;
  1270.     CagdRType
  1271.     LastT = KnotVector[0] - 1.0,
  1272.     *C1Disconts = (CagdRType *) IritMalloc(sizeof(CagdRType) * Length);
  1273.  
  1274.     for (i = Order, Count = 0; i < Length; i++) {
  1275.     if (APX_EQ_EPS(LastT, KnotVector[i], IRIT_EPSILON))
  1276.         Count++;
  1277.     else {
  1278.         Count = 1;
  1279.         LastT = KnotVector[i];
  1280.     }
  1281.  
  1282.     if (Count >= Order - 1) {
  1283.         C1Disconts[C1DiscontCount++] = LastT;
  1284.         Count = 0;
  1285.     }
  1286.     }
  1287.  
  1288.     if ((*n = C1DiscontCount) > 0) {
  1289.     return C1Disconts;
  1290.     }
  1291.     else {
  1292.     IritFree((VoidPtr) C1Disconts);
  1293.     return NULL;
  1294.     }
  1295. }
  1296.  
  1297. /*****************************************************************************
  1298. * DESCRIPTION:                                                               M
  1299. *  Routine to determine where to sample along the provided paramtric domain, M
  1300. * given the C1 discontinuities along it.                     M
  1301. *   Returns a vector of length NumSamples.                     M
  1302. *   If C1Disconts != NULL (NumC1Disconts > 0), C1Discont is being freed.     M
  1303. *                                                                            *
  1304. * PARAMETERS:                                                                M
  1305. *   PMin:            Minimum of parametric domain.                           M
  1306. *   PMax:            Maximum of parametric domain.                           M
  1307. *   NumSamples:      To allocate for the vector of samples.                  M
  1308. *   C1Disconts:      A vector of potential C1 discontinuities in the         M
  1309. *                    (PMin, PMax) domain. This vector is freed by this       M
  1310. *                    routine, if it is not NULL.                             M
  1311. *   NumC1Disconts:   Length of C1Discont. if zero then C1Discont == NULL.    M
  1312. *                                                                            *
  1313. * RETURN VALUE:                                                              M
  1314. *   CagdRType *:    A vector of the suggested set of sampling locations.     M
  1315. *                                                                            *
  1316. * KEYWORDS:                                                                  M
  1317. *   BspKnotParamValues, piecewise linear approximation, knot vectors         M
  1318. *****************************************************************************/
  1319. CagdRType *BspKnotParamValues(CagdRType PMin,
  1320.                   CagdRType PMax,
  1321.                   int NumSamples,
  1322.                   CagdRType *C1Disconts,
  1323.                   int NumC1Disconts)
  1324. {
  1325.     int i, CrntIndex, NextIndex, CrntDiscont;
  1326.     CagdRType Step,
  1327.     *Samples = (CagdRType *) IritMalloc(sizeof(CagdRType) * NumSamples);
  1328.  
  1329.     Samples[0] = PMin;
  1330.     if (NumSamples <= 1)
  1331.     return Samples;
  1332.     Samples[NumSamples - 1] = PMax;
  1333.     if (NumSamples <= 2)
  1334.     return Samples;
  1335.  
  1336.     if (NumC1Disconts > NumSamples - 2) {
  1337.         /* More C1 discontinuities than we are sampling. Grab a subset of    */
  1338.     /* The discontinuities as the sampling set.                 */
  1339.         Step = ((CagdRType) (NumC1Disconts - 1)) / (NumSamples - 2)
  1340.                                 - IRIT_EPSILON;
  1341.     for (i = 0; i < NumSamples - 2; i++)
  1342.             Samples[i + 1] = C1Disconts[(int) (i * Step)];
  1343.     }
  1344.     else {
  1345.     /* More samples than C1 discontinuites. Uniformly distribute the C1  */
  1346.     /* discontinuites between the samples and linearly interpolate the   */
  1347.     /* sample values in between.                         */
  1348.         Step = ((CagdRType) (NumC1Disconts + 1)) / (NumSamples - 2);
  1349.     CrntIndex = CrntDiscont = 0;
  1350.  
  1351.     while (CrntDiscont < NumC1Disconts) {
  1352.         NextIndex = (int) ((CrntDiscont + 1) / Step);
  1353.         Samples[NextIndex] = C1Disconts[CrntDiscont++];
  1354.  
  1355.         for (i = CrntIndex + 1; i < NextIndex; i++) {
  1356.         CagdRType
  1357.             t = (i - CrntIndex) / ((CagdRType) (NextIndex - CrntIndex)),
  1358.             t1 = 1.0 - t;
  1359.  
  1360.         Samples[i] = Samples[CrntIndex] * t1 + Samples[NextIndex] * t;
  1361.         }
  1362.  
  1363.         CrntIndex = NextIndex;
  1364.     }
  1365.  
  1366.     /* Interpolate the last interval: */
  1367.         for (i = CrntIndex + 1; i < NumSamples - 1; i++) {
  1368.             CagdRType
  1369.             t = (i - CrntIndex) / ((CagdRType) (NumSamples - 1 - CrntIndex)),
  1370.             t1 = 1.0 - t;
  1371.  
  1372.             Samples[i] = Samples[CrntIndex] * t1 + Samples[NumSamples - 1] * t;
  1373.         }
  1374.     }
  1375.  
  1376.     if (C1Disconts != NULL)
  1377.     IritFree((VoidPtr) C1Disconts);
  1378.  
  1379.     return Samples;
  1380. }
  1381.  
  1382. /*****************************************************************************
  1383. * DESCRIPTION:                                                               M
  1384. * Given a knot vector, make sure adjacent knots that are close "enough" are  M
  1385. * actually identical. Important for robustness of subdiv/refinement algs.    M
  1386. *                                                                            M
  1387. *                                                                            M
  1388. *                                                                            *
  1389. * PARAMETERS:                                                                M
  1390. *   KV:        Knot vector to make robust, in place.                         M
  1391. *   Len:       Length of knot vector KV.                                     M
  1392. *                                                                            *
  1393. * RETURN VALUE:                                                              M
  1394. *   void                                                                     M
  1395. *                                                                            *
  1396. * KEYWORDS:                                                                  M
  1397. *   BspKnotMakeRobustKVm knot vectors                                        M
  1398. *****************************************************************************/
  1399. void BspKnotMakeRobustKV(CagdRType *KV, int Len)
  1400. {
  1401.     int i;
  1402.  
  1403.     for (i = 1; i < Len; i++)
  1404.     if (KV[i] - KV[i - 1] < KNOT_IS_THE_SAME && KV[i] != KV[i - 1])
  1405.         KV[i] = KV[i - 1];
  1406. }
  1407.